#include <algorithm>
#include <cmath>
#include <cstdio>

const int N = 50010;
int n, m, k, block, sum;
int a[N], cnt[N], ans[N];

struct query {
	int l, r, blo, id;
	bool operator<(const query &a) const {
		return (this->blo == a.blo) ? this->r < a.r : this->l < a.l;
	}
} q[N];

inline void add(int x) {
	sum += cnt[a[x]] * 2 + 1;
	++cnt[a[x]];
}

inline void del(int x) {
	--cnt[a[x]];
	sum -= (cnt[a[x]] * 2 + 1);
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
	freopen("testdata.in", "r", stdin);
	freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
	freopen("P2709.in", "r", stdin);
	freopen("P2709.out", "w", stdout);
#endif
#endif
	scanf("%d%d%d", &n, &m, &k);
	block = sqrt(n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].id = i;
		q[i].blo = q[i].l / block;
	}
	std::sort(q + 1, q + m + 1);
	int L = 1, R = 0;
	for (int i = 1; i <= m; ++i) {
		while (R < q[i].r) add(++R);
		while (L > q[i].l) add(--L);
		while (R > q[i].r) del(R--);
		while (L < q[i].l) del(L++);
		ans[q[i].id] = sum;
	}
	for (int i = 1; i <= m; ++i) {
		printf("%d\n", ans[i]);
	}
	return 0;
}